package com.zjsru.plan2023.oneday;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: cookLee
 * @Date: 2023-11-05
 * 重复的DNA序列:
 * 给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案
 */
public class FindRepeatedDnaSequences {

    /**
     * 根据题意限定长度10
     */
    private static final int TEN = 10;

    /**
     * 主
     * \
     * 输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
     * 输出：["AAAAACCCCC","CCCCCAAAAA"]
     * \
     * 输入：s = "AAAAAAAAAAAAA"
     * 输出：["AAAAAAAAAA"]
     * \
     * @param args args
     */
    public static void main(String[] args) {
        FindRepeatedDnaSequences findRepeatedDnaSequences = new FindRepeatedDnaSequences();
        String s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
        System.out.println(findRepeatedDnaSequences.findRepeatedDnaSequences(s));
    }

    /**
     * 找到重复dna序列
     * 哈希表，循环遍历每一个字串,如果字串的长度超过10，则加入到返回结果
     * @param s s
     * @return {@link List}<{@link String}>
     */
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<>();
        int len = s.length();
        Map<String, Integer> map = new HashMap<>();
        //考虑刚好为10位的时候
        for (int i = 0; i <= len - TEN; i++) {
            int flag = i + TEN;
            String substring = s.substring(i, flag);
            map.put(substring, map.getOrDefault(substring, 0) + 1);
            //重复字符串加入到最后的答案中，重复的只出现一个就好，即value为2
            if (map.get(substring) == 2) {
                ans.add(substring);
            }
        }
        return ans;
    }
}
